#ifndef __MYHASH_HPP__
#define __MYHASH_HPP__

#include <iostream>
#include <vector>
#include <string>


// 简单仿函数实现，这里提供两个：1.数字仿函数  2.字符串仿函数
template<class K>
struct HashFunc
{
    size_t operator()(const K& key)
    {
        return (size_t)key;
    }
};

// 对于字符串仿函数我们做一个特化
template<>
struct HashFunc<std::string>
{
    // 使用bkdr-hash算法实现
    size_t operator()(const std::string& key)
    {
        // 使用一个素数31进行计算
        size_t seed = 31;
        size_t k = 0;
        for (auto a : key)  // hash(abcd) = (a * 31^3 + b * 31^2 + c * 31^1 + d * 31^0) % 4
        {
            k = k * seed + a;
        }
        return k;
    }
};


namespace close_hash
{
    // 闭散列实现哈希表

    // 利用枚举，列举出不同的类型
    enum State
    {
        EMPTY,  // 空
        EXIST, // 存在
        DELETE  // 删除
    };

    // 我们定义数据对象，因为不仅仅需要存储数据，我们还需要其的状态：1.空(默认为空) 2.存在 3.删除(需要和空区别开的原因就是线性探测需要到删除状态)
    template<class K, class V>
    struct HashElem  // 哈希元素
    {
        std::pair<K, V> kv;
        State state = State::EMPTY;  // 默认为空
    };

    // 模板类，我们需要应对不同类型的key-value结构，并且key不一定是size整数，我们需要能够将key转换为一个整数的能力
    // K和V均为类型，hash为对应的仿函数，能够提供解析后的结果
    // 闭散列实现，哈希冲突利用线性探测
    template<class K, class V, class hash=HashFunc<K>>
    class HashTable
    {
    private:
        std::vector<HashElem<K, V>> _data;  // 存放哈希元素的容器，利用STL中的数组
        // 当前容器长度可以由_data.size决定，但是需要存放我们实时的长度，用于计算负载因子，超过了0.7需要进行扩容
        size_t _size;  // 当前负载数
    public:
        // 构造函数，初始化容器长度、以及负载数位0
        HashTable(size_t len = 10)
        :_data(len), _size(0)
        {}
        ~HashTable()
        {}
        bool insert(const std::pair<K, V>& kv);
        bool erase(const K& key);
        HashElem<K, V>* find(const K& key);
        void dilatation();
        // 显示当前负载数：
        size_t size()
        {
            return _size;
        }
        // 当前容量
        size_t capacity()
        {
            return _data.size();
        }
        // 当前负载因子
        double loadfactor()
        {
            return size() * 1.0 / capacity();
        }
    };


    // close_hash实现

    // find查找函数
    // 成功返回HashElem指针，否则nullptr
    template<class K, class V, class hash>
    HashElem<K, V>* HashTable<K, V, hash>::find(const K& key)
    {
        // 根据k，利用hash仿函数找到其整数数值，除留余数法
        size_t len = _data.size();
        if (len == 0) return nullptr;  // 防止data数组为空出现除零错误
        size_t index = hash()(key) % len;

        // 开始线性探测，查找是否存在和key一致的数据元素
        while(_data[index].state != State::EMPTY)
        {
            if (_data[index].state == State::EXIST)
            {
                if (_data[index].kv.first == key) return &_data[index];
            }
            ++index;
            index %= len;  // 防止越界
        }
        return nullptr;  // 没有找到
    }

    // 扩容函数
    // 判断是否扩容函数
    // 如果负载因子（负载数/数组总长度）> 0.7扩容，或者数组长度为空
    template<class K, class V, class hash>
    void HashTable<K, V, hash>::dilatation()
    {
        size_t len = _data.size();
        if (len == 0 || _size*1.0 / len > 0.7)
        {
            // 扩容
            size_t newLen = len == 0 ? 10 : len * 2;
            HashTable<K, V, hash> _hashtable(newLen);  // 提前将空间定为不会发生冲突的状态，所以下面的子对象不会递归dilatation函数的状态
            for (auto& o : _data)
            {
                if (o.state == State::EXIST) _hashtable.insert(o.kv);  // 存在的进行映射即可
            }
            _data.swap(_hashtable._data);  // vector交换即可
        }
    }

    // 插入函数
    // 根据传入的key值，利用hash函数找到唯一的key值在vector进行一个插入
    // 插入元素 防止数据冗余，如果相同key插入拒绝
    template<class K, class V, class hash>
    bool HashTable<K, V, hash>::insert(const std::pair<K, V>& kv)
    {
        // 防止冗余，先进行查找
        if(nullptr != find(kv.first)) return false;  // 已经存在相同的值了
        //无重复值，先查看是否存在扩容，该扩容扩容，防止hash效率低下
        dilatation();
        // 此时映射一个唯一值进行插入
        size_t index = hash()(kv.first) % _data.size();
        while(_data[index].state == State::EXIST)
        {
            ++index;
            index %= _data.size();
        }
        // 此时要么state为空要么是删除的元素，插入即可
        _data[index].kv = kv;
        _data[index].state = State::EXIST;
        ++_size;  // 别忘了增加负载数

        return true;
    }

    // 删除函数
    // 根据传入的key值，对其进行一个删除
    template<class K, class V, class hash>
    inline bool HashTable<K, V, hash>::erase(const K& key)
    {
        // 首先找到此元素
        HashElem<K, V>* elem = find(key);
        if (elem == nullptr) return false;  // 不存在这样的值，无法删除
        // 否则存在，直接置为delete状态即可
        elem->state = State::DELETE;
        --_size;  // 别忘了负载数需要减少
        return true;
    }    
}

namespace open_hash
{
    // 开散列实现哈希，此时为哈希桶，负载因子无须考虑，满了扩充，每次扩充素数个即可。

    // 哈希桶节点
    // T可以代表pair也可以代表K - 适应map、set类型
    template<class T>  
    struct HashBucketNode
    {
        T data;
        HashBucketNode* next = nullptr;
    };

    // 声明
    template<class K, class T, class hash, class KeyofT>
    class HashBucket;

    // 哈希桶内部实现迭代器，因为是无序的，只需要实现++即可
    template<class K, class T, class hash, class KeyofT>
    class __HashBucketIterator
    {
        typedef HashBucket<K, T, hash, KeyofT> Hb;
        typedef HashBucketNode<T> Node;
        typedef __HashBucketIterator<K, T, hash, KeyofT> Self;
    private:
        // Node结点
        Node* _node;
        // 哈希桶对象
        Hb* _hb;
    public:
        __HashBucketIterator(Node* node, Hb* hb)
        :_node(node), _hb(hb)
        {}

        // 提供解引用
        T& operator*()
        {
            return _node->data;
        }
        // ->
        T* operator->()
        {
            return &_node->data;
        }
        // ++ 前置
        Self& operator++()
        {
            // 策略：当前桶查看是否存在，不存在就去找下一个桶
            size_t index = hash()(KeyofT()(_node->data)) % _hb->_data.size();  // 访问的私有部分了，只有朋友才能访问哦~❤
            Node* cur = _node->next;
            while (cur == nullptr)
            {
                if (index + 1 >= _hb->_data.size()) break;
                cur = _hb->_data[++index];
            }
            _node = cur;
            return *this;
        }
        // ==、!=
        bool operator==(const Self& self) const
        {
            return _node == self._node;
        }

        bool operator!=(const Self& self) const
        {
            return !(*this == self);
        }
    };

    // 哈希桶
    template<class K, class T, class hash, class KeyofT>
    class HashBucket
    {
        typedef HashBucketNode<T> Node;

        // 友元类。给予其访问自己秘密的权限
        friend class __HashBucketIterator<K, T, hash, KeyofT>;  // 注意声明模板类的格式
    private:
        std::vector<Node*> _data;
        size_t _size;  // 实际数据个数
    public:
        typedef __HashBucketIterator<K, T, hash, KeyofT> Iterator;  // 迭代器 注意需要公开

        // 构造函数
        HashBucket(size_t len = 11)
        :_size(0)
        {
            _data.resize(len, nullptr);
        }
        // 析构函数
        ~HashBucket()
        {
            // 因为Node节点均为new出来的，所以需要释放其空间
            size_t len = _data.size();
            for (size_t i = 0; i < len; ++i)
            {
                Node* cur = _data[i];
                while (cur)
                {
                    Node* next = cur->next;

                    delete cur;
                    cur = next;
                }
                _data[i] = nullptr;
            }
        }

        // 迭代器相关的
        Iterator begin()
        {
            return Iterator(_data[0], this);
        }

        Iterator end()
        {
            return Iterator(nullptr, this);
        }

        std::pair<Iterator, bool> insert(const T& data);  // 注意，因为maphash重载[]支持元素插入的时候如果是新插入成功，否则返回Iterator
        bool erase(const K& key);
        Iterator find(const K& key);
        // 当前桶的个数
        size_t BucketCount()
        {
            return _data.size();
        }
        // 当前有效数据个数
        size_t size()
        {
            return _size;
        }
    private:
		size_t __stl_next_prime(size_t n);
        void CheckCapacity();
    };

    //// open_hash 定义实现处

    // 每次返回一个素数 - 这样每次摸上一个素数 - 扩容就按这个标准来
    template<class K, class T, class hash, class KeyofT>
    size_t HashBucket<K, T, hash, KeyofT>::__stl_next_prime(size_t n)
    {
        static const size_t __stl_num_primes = 28;
        static const size_t __stl_prime_list[__stl_num_primes] =
        {
            53, 97, 193, 389, 769,
            1543, 3079, 6151, 12289, 24593,
            49157, 98317, 196613, 393241, 786433,
            1572869, 3145739, 6291469, 12582917, 25165843,
            50331653, 100663319, 201326611, 402653189, 805306457,
            1610612741, 3221225473, 4294967291
        };

        for (size_t i = 0; i < __stl_num_primes; ++i)
        {
            if (__stl_prime_list[i] > n)
            {
                return __stl_prime_list[i];
            }
        }

        return -1;  // 扩容的量很大了
    }

    // 扩容函数
    template<class K, class T, class hash, class KeyofT>
    void HashBucket<K, T, hash, KeyofT>::CheckCapacity()
    {
        if (_size == _data.size())
        {
            // 满了，或者为空
            size_t newbucketcount = _size == 0 ? 11 : __stl_next_prime(_size);
            std::vector<Node*> newdata;
            newdata.resize(newbucketcount, nullptr);

            // 每个桶上的每个节点进行重新映射
            // 不可复用insert，复用insert会导致临时对象释放掉指针空间，导致野指针引用哦
            for (size_t i = 0; i < _size; ++i)
            {
                Node* cur = _data[i];

                while (cur)
                {
                    Node* next = cur->next;

                    size_t index = hash()(KeyofT()(cur->data)) % newbucketcount;
                    cur->next = newdata[index];
                    newdata[index] = cur;

                    cur = next;
                }
                _data[i] = nullptr;
            }
            _data.swap(newdata);
        }
    }

    template<class K, class T, class hash, class KeyofT>
    typename HashBucket<K, T, hash, KeyofT>::Iterator HashBucket<K, T, hash, KeyofT>::find(const K& key)  // 注意Iterator前面需要表明是一个类型，即typename，否则编译器识别不出来
    {
        if (_size == 0) return Iterator(nullptr, this);
        size_t index = hash()(key) % _data.size();
        Node* cur = _data[index];

        while(cur)
        {
            if (KeyofT()(cur->data) == key) return Iterator(cur, this);
            cur = cur->next;
        }
        return Iterator(nullptr, this);
    }

    template<class K, class T, class hash, class KeyofT>
    std::pair<typename HashBucket<K, T, hash, KeyofT>::Iterator, bool> HashBucket<K, T, hash, KeyofT>::insert(const T& data)
    {
        Iterator it = find(KeyofT()(data));
        if (it != end()) return std::make_pair(it, false);  // 防止冗余
        CheckCapacity();  // 检查是否需要扩容

        size_t index = hash()(KeyofT()(data)) % _data.size();
        Node* newnode = new Node;
        newnode->data = data;
        // 头插
        newnode->next = _data[index];
        _data[index] = newnode;

        ++_size;
        return std::make_pair(Iterator(newnode, this), true);
    }

    template<class K, class T, class hash, class KeyofT>
    bool HashBucket<K, T, hash, KeyofT>::erase(const K& key)
    {
        if(nullptr == find(key)) return false;// 检查是否存在

        size_t index = hash()(key) % _data.size();
        Node* pre = nullptr;
        Node* cur = _data[index];

        while (cur)
        {
            if (KeyofT()(cur->data) == key)
            {
                // 找到了，判断是什么删除
                if (nullptr == pre)
                {
                    // 头删
                    pre = cur->next;
                    _data[index] = pre;
                    delete cur;
                }
                else
                {
                    // 否则就是中间删
                    pre->next = cur->next;
                    delete cur;
                }
                return true;
            }
            pre = cur;
            cur = cur->next;
        }
        return false;
    }   

}
#endif


///////////////////test///////////
// using namespace std;
// using namespace close_hash;
// using namespace open_hash;

// 整数查找
// void close_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     HashTable<int, int> h;
//     int keyLen = 10;
//     vector<int> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         int key = rand() % 10000, value = rand() % 1999;
//         keyArr[i] = key;
//         h.insert(make_pair(key, value));
//         /////展示阶段
//         cout << "-------------------------\n";
//         cout << "当前插入key-value: " << key << ": " << value << endl;
//         cout << "当前负载数: " << h.size() << endl;
//         cout << "当前容量: " << h.capacity() << endl;
//         cout << "当前负载因子: " << h.loadfactor() << endl;
//         cout << "-------------------------\n"; 
//     }

//     for (int i = 0; i < keyLen; ++i)
//     {
//         HashElem<int, int>* elem = h.find(keyArr[i]);
//         if (elem == nullptr)
//         {
//             cout << "哈希表存在问题，请检查后测试！" << endl;
//             break;
//         }
//         cout << "key: " << elem->kv.first << " value: " << elem->kv.second << endl;
//     }
// }

// 字符串检查
// void close_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     HashTable<string, int> h;
//     int keyLen = 20;
//     vector<string> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         // 生成1~6长度的随机字符串作为key进行测试
//         int num = rand() % 6 + 1;
//         string str;
//         for (int i = 0; i < num; ++i)
//         {
//             int fes = rand() % 26;
//             str += ('a' + fes);
//         }

//         int value = rand() % 1999;
//         keyArr[i] = str;
//         h.insert(make_pair(keyArr[i], value));
//         /////展示阶段
//         cout << "-------------------------\n";
//         cout << "当前插入key-value: " << str << ": " << value << endl;
//         cout << "当前负载数: " << h.size() << endl;
//         cout << "当前容量: " << h.capacity() << endl;
//         cout << "当前负载因子: " << h.loadfactor() << endl;
//         cout << "-------------------------\n"; 
//     }

//         for (int i = 0; i < keyLen; ++i)
//         {
//             HashElem<string, int>* elem = h.find(keyArr[i]);
//             if (elem == nullptr)
//             {
//                 cout << "哈希表存在问题，请检查后测试！" << endl;
//                 break;
//             }
//             cout << "key: " << elem->kv.first << " value: " << elem->kv.second << endl;
//         }
// }

// 实际比较查找时间
// void close_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));

//     HashTable<string, int> h;
//     vector<pair<string, int>> strArr;

//     int keyLen = 20000;
//     strArr.resize(keyLen);

//     vector<string> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         // 生成1~6长度的随机字符串作为key进行测试
//         int num = rand() % 6 + 1;
//         string str;
//         for (int i = 0; i < num; ++i)
//         {
//             int fes = rand() % 26;
//             str += ('a' + fes);
//         }

//         int value = rand() % 1999;
//         keyArr[i] = str;
//         h.insert(make_pair(keyArr[i], value));
//         strArr[i] = make_pair(keyArr[i], value);
//     }

//     pair<string, int> kv;

//     // 随机在数组内查找
//     clock_t time1, time2;
//     clock_t time_strArr = 0, time_closeHash = 0;

//     int n = keyLen;
//     vector<bool> keyexist1(keyLen, false);

//     // 普通数组On遍历
//     while (n)
//     {
//         int num = rand() % keyLen;
//         while (keyexist1[num])
//         {
//             // 找到没有被使用的
//             num = rand() % keyLen;
//         }
//         keyexist1[num] = true;
//         --n;  // 可用下标数减一

//         time1 = clock();
//         for(int i = 0; i < keyLen; ++i)
//         {
//             if (strArr[i].first == keyArr[num]){
//                 kv = strArr[i];
//                 break;
//             }
//         }
//         time2 = clock();
//         time_strArr += (time2 - time1);
//         // cout << "key-value: " << kv.first << ": " << kv.second << endl;
//     }

//     // cout << endl << endl;
//     // 闭散列哈希表查找
//     n = keyLen;
//     vector<bool> keyexist2(keyLen, false);
//     while (n)
//     {
//         int num = rand() % keyLen;
//         while (keyexist2[num])
//         {
//             // 找到没有被使用的
//             num = rand() % keyLen;
//         }
//         keyexist2[num] = true;
//         --n;  // 可用下标数减一

//         HashElem<string, int>* temp;
//         time1 = clock();
//         temp = h.find(keyArr[num]);
//         time2 = clock();
//         time_closeHash += (time2 - time1);
//         kv= temp->kv;
//         // cout << "key-value: " << kv.first << ": " << kv.second << endl;
//     }

//     cout << "----------------------------\n";
//     cout << "time_strArr: " << time_strArr << endl;
//     cout << "time_closeHash: " << time_closeHash << endl;
// }

// 测试插入和删除
// void close_hash_test()
// {
//     HashTable<string, int> h;
//     h.insert(make_pair("你好", 15));
//     h.insert(make_pair("a", 11));
//     h.insert(make_pair("b", 12));
//     h.insert(make_pair("c", 1));
//     h.insert(make_pair("d", 3));
//     h.insert(make_pair("e", 4));
//     h.insert(make_pair("f", 6));
//     h.erase("c");
//     h.insert(make_pair("c", 9));
//     h.insert(make_pair("de", 9));

//     cout << "正常" << endl;
// }

// 整数查找
// void open_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     HashBucket<int, int> h;
//     int keyLen = 10;
//     vector<int> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         int key = rand() % 10000, value = rand() % 1999;
//         keyArr[i] = key;
//         h.insert(make_pair(key, value));
//         /////展示阶段
//         cout << "-------------------------\n";
//         cout << "当前插入key-value: " << key << ": " << value << endl;
//         cout << "当前负载数: " << h.size() << endl;
//         cout << "当前桶数: " << h.BucketCount() << endl;
//         cout << "-------------------------\n"; 
//     }

//     for (int i = 0; i < keyLen; ++i)
//     {
//         HashBucketNode<int, int>* node = h.find(keyArr[i]);
//         if (node == nullptr)
//         {
//             cout << "哈希表存在问题，请检查后测试！" << endl;
//             break;
//         }
//         cout << "key: " << node->kv.first << " value: " << node->kv.second << endl;
//     }
// }

// 字符串检查
// void open_hash_test()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     HashBucket<string, int> h;
//     int keyLen = 20;
//     vector<string> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         // 生成1~6长度的随机字符串作为key进行测试
//         int num = rand() % 6 + 1;
//         string str;
//         for (int i = 0; i < num; ++i)
//         {
//             int fes = rand() % 26;
//             str += ('a' + fes);
//         }

//         int value = rand() % 1999;
//         keyArr[i] = str;
//         h.insert(make_pair(keyArr[i], value));
//         /////展示阶段
//         cout << "-------------------------\n";
//         cout << "当前插入key-value: " << str << ": " << value << endl;
//         cout << "当前负载数: " << h.size() << endl;
//         cout << "当前桶数: " << h.BucketCount() << endl;
//         cout << "-------------------------\n"; 
//     }

//         for (int i = 0; i < keyLen; ++i)
//         {
//             HashBucketNode<string, int>* node = h.find(keyArr[i]);
//             if (node == nullptr)
//             {
//                 cout << "哈希表存在问题，请检查后测试！" << endl;
//                 break;
//             }
//             cout << "key: " << node->kv.first << " value: " << node->kv.second << endl;
//         }
// }

// 两个哈希效率测试
// 以插入、删除、随机查找三种综合效率进行测试
// void hash_efficiency()
// {
//     // 时间种子
//     srand((unsigned int)time(nullptr));
//     // 
//     clock_t time1, time2;
//     clock_t open_insert, close_insert, open_erase, close_erase, open_find, close_find;

//     HashTable<string, int> h1;
//     HashBucket<string, int> h2;

//     int keyLen = 20000;

//     vector<pair<string, int>> keyArr(keyLen);
    
//     for (int i = 0; i < keyLen; ++i)
//     {
//         // 生成1~6长度的随机字符串作为key进行测试
//         int num = rand() % 6 + 1;
//         string str;
//         for (int i = 0; i < num; ++i)
//         {
//             int fes = rand() % 26;
//             str += ('a' + fes);
//         }

//         int value = rand() % 1999;

//         keyArr[i].first = str;
//         keyArr[i].second = value;
//     }

//     // 插入测试
//     // close
//     time1 = clock();
//     for (auto& kv : keyArr)
//     {
//         h1.insert(kv);
//     }
//     time2 = clock();
//     close_insert = time2 - time1;
//     // open
//     time1 = clock();
//     for (auto& kv : keyArr)
//     {
//         h2.insert(kv);
//     }
//     time2 = clock();
//     open_insert = time2 - time1;

//     // 查找测试
//     // close
//     time1 = clock();
//     for (auto& kv : keyArr)
//     {
//         if (!h1.find(kv.first))
//         {
//             cout << "h1: find出错了！" << endl;
//             break;  // 防止刷屏
//         } 
//     }
//     time2 = clock();
//     close_find = time2 - time1;
//     // open
//     time1 = clock();
//     for (auto& kv : keyArr)
//     {
//         if (!h2.find(kv.first))
//         {
//             cout << "h2: find出错了！" << endl;
//             break;  // 防止刷屏
//         } 
//     }
//     time2 = clock();
//     open_find = time2 - time1;

//     // 删除测试
//     time1 = clock();
//     for (auto& kv : keyArr)
//     {
//         h1.erase(kv.first);
//     }
//     time2 = clock();
//     close_erase = time2 - time1;
//     // open
//     time1 = clock();
//     for (auto& kv : keyArr)
//     {
//         h2.erase(kv.first);
//     }
//     time2 = clock();
//     open_erase = time2 - time1;



//     cout << "----------------------------\n";
//     cout << "insert:\n";
//     cout << "\tclose_insert:" << close_insert << endl;
//     cout << "\topen_insert:" << open_insert << endl;
//     cout << "find:\n";
//     cout << "\tclose_find:" << close_find << endl;
//     cout << "\topen_find:" << open_find << endl;
//     cout << "erase:\n";
//     cout << "\tclose_erase:" << close_erase << endl;
//     cout << "\topen_erase:" << open_erase << endl;
//     cout << "综合评价:\n";
//     time_t close_hash = (close_insert+close_find+close_erase);
//     cout << "\tclose_hash: " << close_hash << endl;
//     time_t open_hash = (open_insert+open_find+open_erase);
//     cout << "\topen_hash: " << open_hash << endl;
//     time_t maxi = max(close_hash, open_hash);
//     time_t mini = min(close_hash, open_hash);
//     cout << "时间倍率为: " << maxi / mini << endl;
//     cout << "----------------------------\n";
// }
